package binary_tree.leetcode.medium;

/**
 * @author bruin_du
 * @description 最短的单词编码
 * @date 2022/8/18 22:55
 **/
public class OfferII065_MinimumLengthEncoding {
    TreeNode root;

    class TreeNode {
        TreeNode[] next;
        boolean isEnd;

        public TreeNode() {
            next = new TreeNode[26];
            isEnd = false;
        }
    }

    public int minimumLengthEncoding(String[] words) {
        root = new TreeNode();
        int res = 0;
        for (String str : words) {
            TreeNode cur = root;
            boolean flag = true;
            for ( int i = str.length() - 1; i >= 0; i--) {
                int index = str.charAt(i) - 'a';
                //如果为null，说明还没有来过，创建新结点
                if (cur.next[index] == null) {
                    cur.next[index] = new TreeNode();
                }
                //如果为true，说明有字符串在这里结尾，置为false，并减去这一字符串的长度
                //因为当前字符串要么一样，要么比他长
                else if (cur.next[index].isEnd){
                    cur.next[index].isEnd = false;
                    res -= str.length() - i + 1;
                }
                //如果当前字符串走到末尾，结点的isEnd还是false，说明在该字符串尾部重复
                else if (i == 0 && !cur.next[index].isEnd) {
                    res -= str.length() - i + 1;
                    flag = false;
                }
                cur = cur.next[index];
            }
            //当前字符串在遍历重复的路，不需要置为true
            if (flag) cur.isEnd = true;
            res += str.length() + 1;
        }
        return res;
    }
}
